package 面试经典150题.动态规划;

/**
 * @author tmh
 * @date 2024/7/7 17:02
 * @description
 * k 个房子中最后一个房子是 H
 * k−1
 * ​
 *  。如果不偷这个房子，那么问题就变成在前 k−1 个房子中偷到最大的金额，也就是子问题 f(k−1)。如果偷这个房子，那么前一个房子 H
 * k−2
 * ​
 *   显然不能偷，其他房子不受影响。那么问题就变成在前 k−2 个房子中偷到的最大的金额。两种情况中，选择金额较大的一种结果。
 *
 * 作者：nettee
 * 链接：https://leetcode.cn/problems/house-robber/solutions/138131/dong-tai-gui-hua-jie-ti-si-bu-zou-xiang-jie-cjavap/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class T198打家劫舍 {
    public int rob(int[] nums) {
        if (nums.length==0){
            return 0;
        }
        //k=0的时候，没有房子，所以f(0)=0
        //k=1的时候，只有一间房子，所以f(1)=1
        int n = nums.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        //dp[1]的初始值是第一件房子能够偷盗的价值
        dp[1] = nums[0];
        for (int k = 2; k <= n; k++) {
            //dp[k]表示在前k个房子可以偷盗的金额最大值等于Math.max(在前k-1个房子中能够偷盗的金额最大值,在前k-2个房子中偷盗的金额最大值
            //加上你最后一个房子（下标k-1）之和)
            dp[k]=Math.max(dp[k-1],dp[k-2]+nums[k-1]);
        }
        return dp[n];
    }
}
